\input macros
\tolerance=2500
\def\bookline{\CLOS\  Specification}
\def\chapline{Programmer Interface Concepts}

\beginChapter 1.{Common Lisp Object System Specification}%
{Programmer Interface Concepts}{Programmer Interface Concepts}

Contributors to this document include Daniel G. Bobrow, Linda G.
DeMichiel,\break Richard P. Gabriel, Kenneth Kahn, Sonya E. Keene,
Gregor Kiczales, Larry\break Masinter, David A. Moon, Mark Stefik, and
Daniel L. Weinreb.

Comments and suggestions on this document are encouraged.
Changes will be incorporated over the next several months.
This text will be made available to the X3J13 Committee for the
Common Lisp Standards effort.

\endTitlePage

\beginSection{Introduction}

This proposal presents a description of the standard Programmer 
Interface for object-oriented programming in the \CLOS.    The first 
chapter of this document describes the concepts of the \CLOS, and the
second gives an alphabetic list of functions that comprise the \CLOS\ 
Programmer Interface.    

A second document, ``The \CLOS\ Meta-Object Protocol,'' describes how the
\CLOS\ can be customized to support other existing object-oriented
paradigms and to define new ones.

The fundamental objects of the \CLOS\ are class objects, instances,
generic function objects, and method objects. 

A {\bit class\/} object determines the structure and behavior of a set
of other objects, called its {\bit instances}.  It is an important
feature of the \OS\ that every Common Lisp object is an {\bit
instance\/} of a class.  The class of an object determines the set of
operations that can be performed on the object.

A {\bit generic function} is a function whose behavior depends on the
classes of the arguments supplied to it.  A generic function comprises
a set of {\bit methods\/} (discussed below); these methods define the
class-specific behavior and operations of the generic function.  Thus,
generic functions are objects that may be {\bit specialized} by the
definition of methods to provide class-specific operations.  A generic
function chooses one or more of the set of its methods based on the
classes of its arguments.  A generic function can be used in precisely
the same ways that an ordinary function can be used in Common Lisp; in
particular, a generic function can be used as an argument to {\bf
funcall} and {\bf apply} and can be stored in the symbol-function
cell of a symbol.  The naming conventions for generic functions are
precisely the same as those for ordinary Common Lisp functions.

The class-specific operations provided by generic functions are
themselves defined and implemented by {\bit methods}.  A method---also
called a {\bit method object}---is a function that can be used in any
of the ways that ordinary functions can be used in Common Lisp.  A
method object contains a method function and a set of {\bit parameter
specializers\/} that specify when the given method is applicable.
Each required formal parameter of each method has an associated
parameter specializer, and the method is expected to be invoked only
on arguments that satisfy its parameter specializers.

To summarize, a generic function is a function that contains or
encompasses a number of methods.  The purpose of the generic function
is to provide the object that contains all methods that provide the
pieces of code that define the behavior of the generic function.  When
a generic function is invoked, the classes of its required arguments
determine which methods might be invoked.  The behavior of the generic
function results from which methods are selected for execution, the
order in which the selected methods are executed, and how their values
are combined to produce the value or values for the generic function.
The {\bit method combination\/} facility controls the selection of
methods, the order in which they are run, and the values that are
returned by the generic function.  The \CLOS\ offers a default method
combination type that is appropriate for most user programs.  The
\CLOS\ also provides a facility for declaring new types of method
combination for programs that require them.

\vfill
\endSection%{Introduction}

\beginSection{Classes}

A {\bit class\/} is an object that determines the structure and behavior 
of a set of other objects, called its {\bit instances}.   

Like other objects, all classes are themselves instances of classes.
The class of the class of an object is termed the {\bit metaclass\/}
of that object.  When no misinterpretation is possible, we will also
use the term {\bit metaclass\/} to refer to a class that has instances
that are themselves classes.  The metaclass determines the form of
inheritance used by the classes that are its instances and the
representation of the instances of those classes.  The \CLOS\ provides
a default metaclass that is appropriate for most programs.  The
meta-object protocol allows for defining and using new metaclasses.

A class can include other classes in its definition, in order to inherit
structure and behavior from those classes.  The newly defined class is
called a {\bit subclass\/} of each of the classes that it includes; each
of the included classes is called a {\bit superclass\/} of the
newly defined class.

In situations where it matters whether a class is a direct superclass
or subclass of another, we will use the following terminology.  We
will say that a class, $C\sub{1}$, is a {\bit direct superclass\/} of
a class, $C\sub{2}$, if the definition of $C\sub{2}$ includes
$C\sub{1}$ as a superclass.  We will say that $C\sub{2}$ is a {\bit
direct subclass\/} of $C\sub{1}$.  We will say that a class,
$C\sub{1}$, is a {\bit superclass\/} of a class, $C\sub{n}$, if there
exists series of classes, $C\sub{2},\ldots,C\sub{n-1}$ such that
$C\sub{i+1}$ is a direct superclass of $C\sub{i}$, for $1 \leq i<n$.
In this case, we will say that $C\sub{n}$ is a {\bit subclass\/} of
$C\sub{1}$.  A class is not considered a superclass of itself.  That
is, if $C\sub{1}$ is a superclass of $C\sub{2}$, then $C\sub{1} \neq
C\sub{2}$.  We refer to the set of classes consisting of some given
class $C$ along with all of its superclasses as ``the classes at or
above $C$.''

When a class that includes a set of direct superclasses is defined,
the order in which those direct superclasses are mentioned in the
defining form helps determine a total order on the classes at or above
the newly defined class.  The order of the direct superclasses in the
defining form is called the {\bit local precedence order\/} and will
be discussed below.

Classes are organized into a {\bit lattice}, which gives them a
partial order called the lattice order.  The top of the lattice is the
class named {\bf t} and the bottom is the class named {\bf nil}.  The
lattice order along with the local precedence order mentioned above
can usually be combined to produce a third partial order that can be
embedded in a total order on the classes at or above a given class.
When the lattice and the local precedence order are inconsistent, they
cannot be combined to produce a partial order.  The classes at or
above a given class, placed in a list according to the total order, is
called the {\bit class precedence list}.  When, for a given class, a
total order on the classes at or above a given class cannot be
determined, an error will be signalled during the normal operations of
the \CLOS.  We will normally consider as well-defined only those class
lattices with class precedence lists defined at every class except the
class named {\bf nil}.  The class precedence and its computation will
be discussed at length below.

There is a mapping from the Common Lisp type lattice
into the Common Lisp Object System class lattice.  Many of the standard 
Common Lisp types specified in {\it Common Lisp: The Language\/} by Guy
L. Steele Jr.  have a corresponding class.   Some Common Lisp types do 
not have a corresponding class.   The integration of the type and class 
system is discussed later in this chapter.    

%I removed this text for a couple reasons.   -Sonya 
%First, it's very confusing and doesn't belong so early in the
%introduction.
%Second, I hope we can improve the terminology. 

%The \CLOS\ includes a set of standard objects.  We use the term 
%{\bit standard object\/} to refer to any object whose metaclass is 
%{\bf class}.  The class {\bf object} specifies the default behavior of the
%set of all objects whose metaclass is {\bf class}.  In other words,
%all standard objects inherit (directly or indirectly) from the class
%{\bf object}. 
%
%The \CLOS\ also defines a set of standard classes.  A {\bit standard
%class\/} is any class that is an instance of the class {\bf class}.
%The class {\bf class} is itself of class {\bf class}.  It is therefore
%both a standard class and a standard object.  The class {\bf object}
%is also a standard class since it is also an instance of the class
%{\bf class}.  As a standard object, the class {\bf class} is a
%subclass of the class {\bf object}.
%
%\vfill\eject
%\Vskip 1pc!
%\boxfig
%{\bf\tabskip 0pt plus 1fil
%\halign to \hsize{&#\hfil\cr
%array&hashtable&sequence\cr
%atom*&integer&short-float\cr
%bignum&keyword&simple-array\cr
%bit&list&simple-bit-vector\cr
%bit-vector&long-float&simple-string\cr
%character&nil&simple-vector\cr
%common*&null&single-float\cr
%compiled-function&number&standard-char\cr
%complex&package&stream\cr
%cons&pathname&string\cr
%double-float&random-state&string-char\cr
%fixnum&ratio&symbol\cr
%float&rational&t\cr
%function&readtable&vector\cr
%}}
%\caption{Standard Common Lisp types.  All these types except atom and common have\break
%a corresponding class.}
%\endfig

\beginsubSection{Defining Classes}

The macro {\bf defclass} is used to define a new class.  The syntax for
{\bf defclass} is given in Figure~2-1.   

There are four elements in a {\bf defclass} form.   The first element is
the name of the new class.  

The second element is the superclass list, which specifies the
direct superclasses of the new class.  As mentioned above, the
\CLOS\ determines a class precedence list for the new class.
  The order of the classes in the superclass list in 
the {\bf defclass} form determines a local precedence for classes; that
is, each class in the list must precede all classes to its right in the
final class precedence list.  A detailed explanation of how the class
precedence list is computed is given in the section ``Determining the
Class Precedence List.''

The third element is the set of slot specifiers.  Classes have named
slots, which define the structure of instances of the class.
Each slot specifier includes the name of the slot
and zero or more
slot options.  A slot option pertains only to a single slot.  If 
a local description of a slot is provided, it completely overrides any
description of that slot inherited from a superclass.

The fourth element is the set of class options, which pertain
to the class as a whole.   

The slot options and class options of the {\bf defclass} form allow for 
the following:

\beginlist

\item{\bull} Providing an initial value form for one or more slots.
If an initial value form is supplied for a slot, when an
instance is created the initial value form is evaluated to produce a value
that is given to that slot. 

\item{\bull} Requesting that methods for appropriately named generic functions
be automatically generated for reading or accessing one or more slots. 

\item{\bull} Controlling whether one copy of a given slot is
shared by all instances or each instance has a copy of that
slot.  

\item{\bull} Requesting that a constructor function be automatically
generated for making instances of this class.

\item{\bull} Indicating that the instances of this class are to have a
metaclass other than the default.
\endlist 

%[The following isn't true, since the class precedence list includes
%the class
%itself, which is not in the transitive closure of all the classes in the 
%includes list.  -Sonya ]
%The transitive closure of all the classes in the {\it includes\/} list
%specifies all the classes that this class inherits from.  An ordering of
%this list for purposes of precedence is called the {\bit class
%precedence list}. 

%[I don't think we should discuss the class precedence list in detail here. -Sonya] 
%The new class created by {\bf defclass} is a subclass of all the
%classes specified in the {\it includes\/} list of the {\bf defclass}
%form.  A class that is defined in this way is the most specific 
%element of a sublattice from which descriptions are inherited.  

\beginsubSection{The Structure of Instances}

The definition of the class specifies the structure of instances of 
the class.   The slots define the structure of the instance.  

There are two kinds of slots.  An {\bf :instance} slot is a place where 
data is stored in an instance.  This is the most commonly used 
kind of slot---each instance has an individual slot of the same 
name.  A {\bf :class} slot is a place where data is stored in a 
class.  There is only one slot, whose value is shared by all instances 
of the class.   The {\bf :allocation} slot option specifies whether the 
slot is an {\bf :instance} slot or a {\bf :class} slot. 

\endsubSection%{The Structure of Instances}

\beginsubSection{Creating Instances of Classes}

The function {\bf make-instance} creates and returns a new instance of a
class.   If the {\bf defclass} form indicates that some of the slots are
initializable, {\bf make-instance} accepts arguments specifying the slots to
initialize and the initial values.    

The initialization protocol is not yet specified. 

\endsubSection%{Creating Instances of Classes}

%[I don't think we need this section.  -Sonya]
%\beginsubSection{Superclasses}
%
%\endsubSection%{Superclasses}

\beginsubSection{Accessing Slots}

Slots can be accessed in two ways: by use of the accessors defined in  
the {\bf defclass} form and by use of the primitive function 
{\bf slot-value}.   

The {\bf defclass} syntax allows for generating generic functions for
readers and accessors---these can be specified for individual slots or for
all slots. When a reader or accessor is requested for an individual slot,
the name of the generic function is directly specified; when readers and
accessors are requested for all slots, the names of the generic functions
are determined by combining a prefix and the individual slot names.  If an
accessor is requested, a method is automatically generated for reading the
value of the slot, and a {\bf setf} method for it is also generated.  If
a reader is requested, a method is automatically generated for reading the
value of the slot, but no {\bf setf} method for it is generated.  
These methods are added to the appropriate generic functions.

The function {\bf slot-value} can be used with any of the slot names 
specified in the {\bf defclass} form to access a specific slot in an
object of the given class.  If the object has no such slot, an error is 
signalled.   Note that {\bf slot-value} can be used to read or write the
value of a slot whether or not the {\bf defclass} form specified
any accessor functions for that slot.   When
{\bf slot-value} is used, no methods for the accessors are executed. 

The automatically-generated accessors specified in the {\bf defclass} 
form are generic functions that are implemented using {\bf 
slot-value}.

Sometimes it is convenient to access slots from within the body of a method
or function.  The macro {\bf with-slots} can be used to set up a lexical
environment in which certain slots are lexically available.   {\bf
with-slots} enables one to specify whether the accessors or {\bf
slot-value} should be used to access the slots.

\endsubSection%{Accessing Slots}
\endSection%{Classes}

\beginSection{Inheritance}

Inheritance is the key to program modularity within \CLOS.  A typical
object-oriented program consists of several classes, each of which
defines some aspect of behavior.  New classes are defined by including
the appropriate classes as superclasses, thus gathering desired aspects
of behavior into one class.

A class inherits methods, slots, and some {\bf defclass} options from all of
its superclasses.  However, the class can choose to override an 
inherited method, slot, or {\bf defclass} option.  This section describes what
is inherited from superclasses, and how a class can override an aspect
of inherited behavior.  
 
\beginsubSection{Inheritance of Methods}

In general, methods are inherited by subclasses.   That is, a method provided by a
class is applicable for use on instances of any subclass of that 
class.   In some cases, an inherited method can be shadowed by providing
a method for a more specific class.   When standard method combination
is used, the primary method can be shadowed by a method on a more
specific class.   (However, if the more specific method uses
{\bf call-next-method}, the next most specific primary method is called.)

The inheritance of methods acts the same way regardless of whether the 
method was created using {\bf defmethod} or by using one of the {\bf defclass} 
options that cause methods to be generated automatically (for reading or 
accessing the value of a slot). 

The inheritance of methods is described in detail in the section
``Method Selection and Combination.''   

\endsubSection%{Inheritance of Methods}

\beginsubSection{Inheritance of Slots}

In general, slots are inherited by subclasses.   That is, slots defined in 
a class are usually also slots in any subclass of that class. 
The inheritance of slots
depends on whether the inherited slot is allocated by {\bf :class} or
{\bf :instance}, and whether the {\bf :allocation} slot option is given in the local
slot-description.   One important rule is that 
an instance has at most one slot by any given name accessible to it. 
There are several different cases:

1.  In the simplest case, a class does not provide a local description
of a slot with the same name as a slot provided by its superclass.  If 
it is an {\bf :instance} slot, the subclass allocates storage for it in each
instance.  If it is a {\bf :class} slot, the allocation of the slot is done by 
the superclass, and that single slot is accessible by instances of both 
the superclass and the subclass.  

2.  Whenever a class specifies {\bf :allocation} {\bf :class},
a new {\bf :class} slot is created, and any slot with that name provided 
by a superclass is not accessible to instances of this class.

3.  Whenever a class specifies {\bf :allocation} :none for a slot, no slot
with that name is accessible to instances of this class.  Thus, the
{\bf :allocation} :none option allows for subtractive inheritance; a class can
specify {\bf :allocation} :none to prevent access to a slot supplied by a 
superclass.

4.  Whenever a class provides a local description of an {\bf :instance} slot,
and its superclass provides a description of a {\bf :class} slot with  
the same name, only the {\bf :instance} slot that was described locally
is accessible to the subclass.   Only the {\bf :class} slot is accessible  
instances of the superclass.   (Note that the {\bf defclass} default {\bf :allocation}
is {\bf :instance}, so a slot description is treated as an {\bf :instance} slot 
if the {\bf :allocation} option is not explicitly supplied.)

5.  Whenever a class provides a local description of an {\bf :instance} slot,
and its superclass also provided a description of an {\bf :instance} slot with
the same name, the effect of the local slot description is to override
or alter some of the inherited characteristics of the slot, such as its
{\bf :initform} or {\bf :type} options.  (The inheritance behavior of each {\bf defclass}
option is described further on in this section.)

The wording of the above cases mentions one subclass and one superclass,
but a class often has more than one superclass.   The class precedence
order is used to determine how the slots are inherited.  When a class is
defined, the slots that it will be able to access are determined by
considering each local slot-description, and the description of each
slot that is given by the most specific superclass in the class
precedence list.   The examples further on in this section should
clarify this behavior.

\endsubSection%{Inheritance of Slots}

\beginsubSection{Inheritance of defclass Options}

Inheritance of Slot-options: 

{\bf :accessor} -- This option is not inherited; that is, subclasses do not 
automatically generate methods for accessing a slot unless the {\bf :accessor} 
prefix is specified in the local description.   However, a subclass does  
inherit the methods generated by this option, in the sense that the 
methods are applicable for instances of the subclass.   Because these
methods are primary methods, when standard method combination is used
the subclass can shadow the inherited methods by providing more specific
methods, either by using the {\bf :accessor} option or using {\bf defmethod}.   The
type of inheritance described here also applies to the methods generated
by the {\bf :reader}, {\bf :accessor-prefix}, and {\bf :reader-prefix} options.

{\bf :reader} -- This slot option is not inherited; see the description of the
{\bf :accessor} slot-option.

{\bf :allocation} -- This option is not inherited by subclasses.  However, if 
a local slot description is given for a slot with the same name as a
slot provided by a superclass, this option affects the inheritance of
the slot.  The semantics of slot inheritance and the {\bf :allocation} option
are described above.

{\bf :initform} -- The {\bf :initform} 
option is inherited, and can be overridden in 
a straightforward way.  In the case of an inherited {\bf :instance} slot, if
the {\bf :initform} option is given in a local description, the local
{\bf :initform} completely overrides the inherited {\bf :initform}.

{\bf :type} -- The {\bf :type} option is inherited as follows.   When a class is
being defined, the slot descriptions of all of its superclasses
(including itself) are considered, regardless of the allocation of the
slot. The type of the value of the slot is constrained to satisfy all of
the type constraints given in the descriptions of each of its
superclasses, including itself.  That is, if T1, T2 and so on are the
type constraints given by the class and all of its superclasses, the
value of the slot must satisfy (typep value '(and T1 T2 T3...).  [This 
inheritance behavior allows a compiler to optimize on the basis of the
{\bf :type} option in the {\bf defclass} form.   Some operations can be improved,
when the slot directly is involved in an arithmetic expression, such as
being able to emit the machine addition instruction with only overflow
checking.]

Inheritance of Class Options:

{\bf :accessor-prefix} -- This slot option is not inherited; see the
description of the {\bf :accessor} slot-option. 

{\bf :reader-prefix} -- This slot option is not inherited; see the description
of the {\bf :accessor} slot-option.

{\bf :constructor} -- This option has no effect on subclasses; it is not
inherited.   

{\bf :documentation} -- This option has no effect on subclasses; it is not
inherited.  

{\bf :metaclass} -- This option has no effect on subclasses; it is not
inherited.

\endsubSection%{Inheritance of defclass Options}

\beginsubSection{Examples of Inheritance}

\screen!

(defclass C1 () ((S1 :initform 5.4 :type number) 
                 (S2 :allocation :class))

(defclass C2 (C1) ((S1 :initform 5 :type integer)
                   (S2 :allocation :instance)
                   (S3 :accessor C2-S3))
  :reader-prefix C2-) 

(defclass C3 (C2) ((S2 :allocation :none))) 

\endscreen!

C1 has an {\bf :instance} slot named S1, whose default initial value is 5.4, 
and whose value is constrained to be a number.   C1 also has a {\bf :class} 
slot named S2.

C2 has access to an {\bf :instance} slot named S1, whose default initial value 
is 5, and whose value is constrained to satisfy 
(typep value '(and integer number)).  
C2 has access to two {\bf :instance} slots, named S1 and
S2.  C2 has methods defined for reading the value  
of its slots; these methods are for the generic functions named:  C2-S1,
C2-S2, and C2-S3.  There is also a SETF method for use with C2-S3.

C3 has access to an {\bf :instance} slot named S1, whose default initial value
is 5, and whose value is constrained to satisfy (typep value '(AND
integer number)).  C3 also has access to a slot named S3.  C3 has  
methods applicable for reading the value of the slots S1, S2, and S3.  
Note that although C3 has a method for reading the value of slot S2, it 
does not have access to that slot, so using the method would result in 
an error.  

\endsubSection%{Examples of Inheritance}

\endSection%{Inheritance}

\beginSection{Integrating Types and Classes}

The \CLOS\ maps the Common Lisp type space into the space of classes.
Many but not all of the predefined Common Lisp type specifiers have a
class associated with them.  For example, an array is of type {\bf
array}, and of class {\bf array}.  Every class has a corresponding type. 

A class that corresponds to a predefined Common Lisp type is
called a {\bit standard type class}.  Each standard type class has the
class {\bf standard-type-class} as a metaclass.   Users can write methods that
discriminate on any primitive Common Lisp type that has a corresponding class.
However, it is not allowed to make an instance of a standard type class 
with {\bf make-instance} or to include a standard type class as a 
superclass of a class.  Figure~1-1 lists the standard type classes.
Figure~1-2 displays part of the lattice of standard-type-classes.

[Figure 1-1, standard type classes, should go here.
Caption:  Standard type classes.  These classes correspond to predefined
Common Lisp types.  The class nil has no instances.]

Creating a type by means of {\bf defstruct} creates a class in this
lattice.  Such a class is an instance of {\bf structure-class} and a
direct subclass of the class that corresponds to the type given as
its {\bf :includes} argument.  If no classes are included, the new class
is a direct subclass of the class {\bf t}.

%Removed because the Figure 1-2 should show the ordering.   -Sonya
%Will you fix it to reflect only those types that have classes?   
%Converting a partial ordering to a total ordering for the sake of brevity,
%classes are ranked here in order from most specific to least specific:
%
%{\bf rational} {\bf float} {\bf number} {\bf symbol} {\bf list} {\bf
%vector} {\bf array} {\bf sequence}  

%Removed because we aren't having classes for all these types.  -Sonya 
%The following precedence relations hold among classes:
%{\bf list} has precedence over {\bf symbol} (for {\bf nil});
%{\bf array} has precedence over {\bf sequence} (for vectors);
%{\bf vector} has precedence over {\bf simple-array} (for simple-vectors);
%{\bf bit-vector} has precedence over {\bf simple-array} (for simple-bit-vectors);
%and {\bf string} has precedence over {\bf simple-array} (for simple-strings).
 
%Removed because the idea of abstract classes is gone.   -Sonya 
%The classes {\bf number}, {\bf integer}, {\bf rational}, {\bf float},
%{\bf list}, and {\bf sequence} are {\bit abstract classes}, that is,
%they can never be directly instantiated.  The function {\bf class-of}
%will never return one of these classes.

\eject
\beginsubSection{Lattice of classes that are instances of standard-type-class}

Note: This figure must be changed to remove the types that are not
going to have a class associated with them.  

\fig{
\def\IgnoreLineBreaks{\catcode'15=9     \catcode'12=9}
\def\IgnoreWhiteSpace{\catcode'11=9 \catcode'40=9 \IgnoreLineBreaks}
\def\DontIgnoreWhiteSpace{\catcode'12=\active\catcode'15=5\catcode'11=10\catcode'40=10}

\font \pipefont= circlew10
\font \foofont = amr10 at 1sp

\IgnoreWhiteSpace

\let \adv=\advance
\def\he{height}
\def\wi{width}
\def\de{depth}

\newdimen \stroke       
\stroke= \fontdimen8\pipefont   % thickness of line in circles
\newdimen \radius       \radius=6pt     % radius of circles

\newdimen\irad \irad=\radius\advance\irad by -.5\stroke
\newdimen\orad \orad=\radius\advance\irad by  .5\stroke

\newbox\BStrutbox

\setbox\BStrutbox\hbox{\vrule\wi0pt\he8.5pt\de8.5pt}
\def\BoxStrut{\unhcopy\BStrutbox}

% Arrows

\newdimen\ArrowShift
\ArrowShift=\fontdimen22\tensy
\advance\ArrowShift by -0.5\stroke

\def\StrikeOut #1
{       \setbox0\hbox{#1}
        \hbox to 1\wd0
        {       \vrule \he\stroke\de0pt\wi\wd0
                \hskip-\wd0
                \unhbox0
        }
}

\def\LeftArrow
{       \hskip 0.5\stroke
        \StrikeOut{\lower\ArrowShift\hbox to 10pt{\tensy\char'40\hss}}
}

\def\RightArrow
{       \StrikeOut{\lower\ArrowShift\hbox to 10pt{\hss\tensy\char'41}}
        \hskip 0.5\stroke
}

\def\ArrowLine
{       \StrikeOut{\hskip 10pt\hskip 0.5\stroke}
}

\def\LeftToRight
{       \let\RightSideArrow=\ArrowLine
        \let\LeftSideArrow=\RightArrow
}

\def\RightToLeft
{       \let\LeftSideArrow=\ArrowLine
        \let\RightSideArrow=\LeftArrow
}

\def\NoArrows
{       \let\LeftSideArrow=\ArrowLine
        \let\RightSideArrow=\ArrowLine
}
% boxes around tokens

\let\NonterminalFont=\tenrm

\newbox\TStrutbox
\setbox0\hbox{\NonterminalFont{Bg}}
\setbox\TStrutbox\hbox{\vrule\wi0pt\he\ht0\de\dp0}
\def\TextStrut{\unhcopy\TStrutbox}

\def\HorzLine{\hrule \he \stroke \de 0pt}
\def\HFil{\leaders\HorzLine\hfil}
\def\HFill{\leaders\HorzLine\hfill}

\def\Nonterminal#1
{\setbox1\vbox to 0pt{
        \vss
        \hbox{\TextStrut\NonterminalFont\space#1\space\hskip-\stroke}
        \vss}
        \hbox{
        \BoxStrut
        \LeftSideArrow
        \lower\irad\vbox{
                \TopSquare
                \copy1
                \BotSquare}
        \RightSideArrow}
}

\def\TopSquare
{       \hbox{
        \vrule\he\stroke\de\irad\wi\stroke
        \vrule\he\stroke\de0pt\wi\wd1
        \vrule\he\stroke\de\irad\wi\stroke}
}

\def\BotSquare
{       \hbox{
        \vrule\he\orad\de0pt\wi\stroke
        \vrule\he\stroke\de0pt\wi\wd1
        \vrule\he\orad\de0pt\wi\stroke}
}

\def\\#1{\Nonterminal{#1}\HFil}
\def\last#1{{\def\RightSideArrow{}\Nonterminal{#1}}}

% piping

\def\foo{\rlap{\foofont\char'40}}
\def\foo{}

\def\FulVert{\vrule             \wi\stroke\foo\hskip-\stroke}
\def\TopVert{\vrule\de-\irad    \wi\stroke\foo\hskip-\stroke}
\def\BotVert{\vrule\he-\orad    \wi\stroke\foo\hskip-\stroke}

\def\Center#1,#2.
{\hskip\radius\foo#1\lower.5\stroke\hbox{\pipefont#2}\hskip\radius}

\def\ru{\char'10\hskip -2\radius}
\def\rd{\char'11\hskip -2\radius}
\def\ld{\char'12\hskip -2\radius}
\def\lu{\char'13\hskip -2\radius}
\def\thru{\hskip-\radius\vrule\he\stroke\de0pt\wi2\radius\hskip\radius\hskip-2\radius}

\def\Center#1,#2.
{\foo\hskip\radius#1{\pipefont#2\unskip}\hskip-\radius}

\def\LT{\Center\BotVert,\lu.}
\def\LU{\Center\FulVert,\lu.}
\def\LL{\Center\FulVert,\ld.}
\def\LB{\Center\TopVert,\ld.}
\def\LMid{\Center\TopVert\BotVert,\rd\ru\thru.}
\def\LMU{\Center\TopVert,\rd\thru.}
\def\LML{\Center\BotVert,\ru\thru.}
\def\LFD{\Center\FulVert,\ru\thru.}
\def\LS{\Center\TopVert\BotVert,\rd\ru.}

\def\RT{\Center\BotVert,\ru.}
\def\RU{\Center\FulVert,\ru.}
\def\RL{\Center\FulVert,\rd.}
\def\RB{\Center\TopVert,\rd.}
\def\RMid{\Center\TopVert\BotVert,\ld\lu\thru.}
\def\RMU{\Center\TopVert,\ld\thru.}
\def\RML{\Center\BotVert,\lu\thru.}

\def\Cross{\Center\FulVert,\thru.}
\def\LR{\Center,\thru.}
\def\TB{\Center\FulVert,.}
%  ShiftBox

\newbox\x
\newbox\y
\newbox\tempy
\newbox\z
\newbox\tempz

\def\ShiftBox#1{
\savemod
\saverulebox
\setbox\x
\vbox{  \everycr{\noalign{{\modifyrulebox\global\setbox\z\hbox{}}}}
        \halign{&\setbox\x\hbox{##}
        \global \setbox\z\hbox{\unhbox\z\vrule\he\ht\x\de\dp\x\wi0pt}
                \unhbox\x
                \cr
                #1}}%
\lower\ht\y\box\x\HFil
\restoremod
\restorerulebox
}

\def\saverulebox{
        \setbox\tempy\box\y
\global \setbox\y\vbox{}
        \setbox\tempz\box\z
\global \setbox\z\hbox{}
}

\def\restorerulebox{
\global \setbox\y\box\tempy
\global \setbox\z\box\tempz
}

\def\topmod{}

\def\thisrow{\global\let\modifyrulebox\firstmod}

\def\firstmod{
        \global\setbox\y\vbox{\hrule\he0pt\wi0pt\de\dp\z}
        \global\let\modifyrulebox\latermod
}
\def\latermod{
        \global\setbox\y\vbox{\unvbox\y\hrule\he\ht\z\de\dp\z\wi0pt}
}
\def\savemod{
        \let\tempmod\modifyrulebox
\global \let\modifyrulebox\topmod
}
\def\restoremod{
\global\let\modifyrulebox\tempmod
}

\DontIgnoreWhiteSpace
{\baselineskip0pt
\lineskip0pt
\LeftToRight
\IgnoreWhiteSpace

\def\ms{\os\os\os\os}
\def\os{\omit\span}
\hbox{
\\{NIL}
\ShiftBox{
    \ms\LT\\{bit}&\RT\cr
    \ms\ShiftBox{
        \ShiftBox{
            \ShiftBox{
                \LU\\{fixnum}&\RT\cr
                \LU\\{bignum}&\RMU\thisrow\cr
                }\\{integer}&\RML\thisrow\cr
            \LU\\{ratio}&\RB\cr
            }\\{rational}&\RT\cr
        \ShiftBox{
            \LU\\{short-float}&\RT\cr
            \LU\\{single-float}&\RMid\thisrow\cr
            \LU\\{double-float}&\RL\cr
            \LU\\{long-float}&\RB\cr
            }\\{float}&\RMid\thisrow\cr
        \LU\\{complex}&\RB\cr
        }\\{number}&\RU\cr
    \ms\LU\\{standard-char}\\{string-char}\\{character}&\RU\cr
    \LU\\{keyword}&\os\os\os\RML\\{symbol}&\RU\cr
    \LU\\{null}&\os\os\os\LS&\TB\cr
    \LMid\\{cons}&\os\os\RMU\\{list}&\RML\\{sequence}&\RMid\thisrow\cr
    \os\LL\\{simple-vector}&\LML\HFil&\RML\\{vector}&\LS&\TB\cr
    \os\LL\\{simple-bit-vector}&\LFD\\{bit-vector}&\RL&\TB&\TB\cr
    \os\LL\\{simple-string}&\LFD\\{string}&\RB&\TB&\TB\cr
    \os\TB&\os\LB\HFil\\{simple-array}&\RMU\\{array}&\RL\cr
    \ms\LL\\{stream}&\RL\cr
    \ms\LL\\{hashtable}&\RL\cr
    \ms\LL\\{readtable}&\RL\cr
    \ms\LL\\{package}&\RL\cr
    \ms\LL\\{pathname}&\RL\cr
    \ms\LL\\{function}&\RL\cr
    \ms\LL\\{compiled-function}&\RL\cr
    \ms\LB\\{random-state}&\RB\cr
}
\last{T}}}
\hbox{}
}\caption{This figure shows all required subclass relationships among the classes that\break
are instances of
standard-type-class, with the exception of classes defined by means of\break
defstruct.  Implementations may choose to impose additional ones.}
\endfig

\endsubSection%{Types and Classes}
\endSection%{Integrating Types and Classes}


\beginSection{Determining the Class Precedence List}

The {\bit class precedence list} is a total order on the set of
classes at or above a given class; the total order is expressed as a
list.  A class precedence list is used in several ways.  The method
selection and combination process uses the class precedence list to
order methods from most specific to least specific.  When one class
has several superclasses, a more specific class can override some of
the options declared in the {\bf defclass} form of a less specific
class.  Some options are not inherited and therefore need not be
overridden.

\beginsubSection{Computing the Class Precedence List}

The class lattice imposes a partial ordering on the classes in the
lattice, called the {\bit lattice order}.  This partial ordering is
generated by
a set of ordered pairs of classes called $R\sub l$
where $$R\sub l=\{(C\sub
1,C\sub 2)\,|\,\hbox{$C\sub 2$ is a direct superclass of $C\sub 1$}\}$$
The lattice order is the transitive closure of $R\sub l$.

The {\bf defclass} form for a class provides a total ordering on the
direct superclasses for that class, called the {\bit local precedence order\/};
the local precedence order is an ordered list of the direct superclasses
of a class.  We form a second partial ordering from the set of local
precedence orders in the class lattice.  This second partial ordering
is generated by a set of ordered pairs of classes called
$R\sub p$.  For every class $C$, if the local precedence order for that
class is $(C\sub 1\ldots C\sub n)$, then $(C\sub i,C\sub {i+1})\in
R\sub p$ for $1\leq i<n$.

We define a set called $R=R\sub l\cup R\sub p$.
$R$ may or may not generate a partial ordering depending
on whether $R\sub l$ and $R\sub p$ are
consistent; we assume they are consistent and that $R$ is a partial
ordering. When $(C\sub 1,C\sub 2)\in R$ we say that $C\sub 1$ {\bit
precedes} $C\sub 2$.

Let $S\sub C$ be the set of classes at or above $C$; let $R'$ be
the subset of $R$ where $$R'=\{(C,D)\,|\,\hbox{$C\in$ $S\sub
C$ and $D\in$ $S\sub C$}\}$$ 

That is, $R'$ contains the pairs
that involve the classes in $S\sub C$.  To compute the class
precedence list at $C$, we topologically sort the elements of 
$S\sub C$ with
respect to the partial ordering $R'$.   When the topological sort
would non-deterministically select a class from a set of classes none
of which are preceded by other classes with respect to $R'$, the class
that appears first in a preorder treewalk is selected.
We require that an implementation of \CLOS\ signal an error if the
partial ordering is inconsistent.

\beginsubsubsection{Topological Sorting}

Topological sorting proceeds by finding a class $C$ in~$S\sub C$
such that no other class precedes that element according to the
elements in~$R'$.  $C$ is placed first in the result.  We remove $C$ from
$S\sub C$, and we remove all relations of the form $(C,D)$,
$D\in S\sub C$, from $R'$. We repeat the process, adding
classes with no predecessors at the end of the result.  We stop when
no element can be found that has no predecessor.

If $S\sub C$ is not empty and the process has stopped, the
order $R$ is inconsistent: if every class in the finite set of classes
is preceded by another, then the relation contains a loop, and there
are two classes, $C\sub 1$ and $C\sub 2$, such that $C\sub 1$ precedes
$C\sub 2$ and $C\sub 2$ precedes $C\sub 1$.

Sometimes there are several classes from $S\sub C$ with no
predecessors, and in this case we select the one that appears first in
a preorder treewalk starting at $C$.

A preorder treewalk is defined in terms of the order in which classes
are visited while performing a process
called ``walking from a class.''  The following is a recursive
definition of walking from a class.  Let $C$ be a class and let
$\{C\sub 1\ldots C\sub n\}$ be its direct superclasses in the local
precedence order.  Nodes are visited unless they have already been
visited.  To walk from $C$, first $C$ is visited, then we walk from
$C\sub 1$, then we walk from $C\sub 2$, and so on until we finally
walk from $C\sub n$.

\endsubsubsection%{Topological Sorting}

\beginsubsubsection{Examples}

Here is an example of determining a class precedence list.  The classes
are defined:

\screen!

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())
\endscreen!

The set $S$~$=$ $\{${\tt pie apple cinnamon fruit spice food}$\}$. The
set $R'$~$=$ $\{${\tt (pie, apple) (pie, cinnamon)
(apple, cinnamon) (apple, fruit) (cinnamon, spice)
(fruit, food) (spice, food)}$\}$.

The class {\tt pie} is not preceded by anything, so it comes first;
the result so far is {\tt (pie)}.  We remove {\tt pie} from $S$ and
relations mentioning {\tt pie} from $R'$ and get $S$~$=$ $\{${\tt
apple cinnamon fruit spice food}$\}$ and $R'$~$=$ $\{${\tt
(apple, cinnamon) (apple, fruit) (cinnamon, spice)
(fruit, food) (spice, food)}$\}$.

The class {\tt apple} is not preceded by anything, so it is next; the
result is {\tt (pie apple)}. Removing {\tt apple} and the relevant
relations we get $S$~$=$ $\{${\tt cinnamon fruit spice food}$\}$ and
$R'$~$=$ $\{${\tt (cinnamon, spice) (fruit, food)
(spice, food)}$\}$.

The classes {\tt cinnamon} and {\tt fruit} are not preceded by
anything, so we look at which of these two comes first in the preorder
treewalk. The preorder treewalk visits classes in this order: {\tt
pie}, {\tt apple}, {\tt fruit}, {\tt food}, {\tt cinnamon}, {\tt
spice}.  Therefore we select {\tt fruit} next, and the result so far
is {\tt (pie apple fruit)}.  $S$~$=$ $\{${\tt cinnamon spice
food}$\}$; $R'$~$=$ $\{${\tt (cinnamon, spice) (spice, food)}$\}$.

The class {\tt cinnamon} is next, giving the result so far as {\tt (pie apple
fruit cinnamon)}.  $S$~$=$ $\{${\tt spice food}$\}$; $R'$~$=$
$\{${\tt (spice, food)}$\}$.

The classes {\tt spice} and {\tt food} are added in that order, and the class
precedence list is {\tt (pie apple fruit cinnamon spice food)}.

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

\screen!

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())
\endscreen!

The class {\tt fruit} must precede {\tt apple} because the local
ordering of superclasses is preserved.  The class {\tt apple} must
precede {\tt fruit} because a class always precedes its own
superclasses.  When this situation occurs, an error is signalled when
the system tries to compute the class precedence list.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

\screen!

(defclass pie (apple cinnamon) ())

(defclass pastry (cinnamon apple) ())
\endscreen!

The ordering for {\tt pie} is:  {\tt (pie apple cinnamon)}  

The ordering for {\tt pastry} is:  {\tt (pastry cinnamon apple)}

There is no problem with the fact that {\tt apple} precedes {\tt
cinnamon} in the ordering of the superclasses of {\tt pie}, but not in the
ordering for {\tt pastry}.  However, it is not possible to build a new class
that has both {\tt pie} and {\tt pastry} as superclasses.

\endsubsubsection%{Examples}

\endsubSection%{Computing the Class Precedence List}

\endSection%{Determining the Class Precedence List}


\beginSection{Generic Functions and Methods}

\beginsubSection{Introduction to Generic Functions}

Like an ordinary Lisp function, a generic function takes arguments,
performs an operation, and perhaps returns useful values.  An ordinary
function has a single body of code that is always executed when the
function is called.  A generic function might perform a different
series of operations and combine the results of the operations in
different ways, depending on the class of one or more of its
arguments.  An argument that determines which method or methods are to
be run is called a {\bit specialized argument\/}.  A generic function
can have several methods associated with it, and the class of each
specialized argument to the generic function indicates which method or
methods to use.  The generic function is said to {\bit discriminate}
on the classes of its arguments.

Ordinary functions and generic functions are called with identical
syntax:

{\tt ({\it function-name arguments} $\ldots$ )}
 
Generic functions are not only syntactically compatible with ordinary
functions; they are semantically compatible as well:

\beginlist

\item{\bull} They are true functions that can be passed as arguments and
used as the first argument to {\bf funcall} and {\bf apply}.

\item{\bull} Generic functions are named precisely as are ordinary
functions. When a generic function is associated with a symbol, that name
is in a certain package and can be exported if it is part of an external
interface.  This allows programmers to keep unrelated programs separate.

\endlist

Ordinary functions have a definition that is in one place; generic
functions have a distributed definition.  The definition of a generic
function can be found in a set of {\bf defmethod} forms, possibly along
with a {\bf defgeneric-options} form that provides information about the
contract of the generic function.  Evaluating these forms produces a
generic function object.  Typically a generic function object is stored as
the function definition of the symbol that is the name of the generic
function.

When a new {\bf defgeneric-options} form is evaluated and the generic function
of this name already exists (that is, the function definition of the
first subform of {\bf defgeneric-options} is a generic function object), the
existing generic function object is modified.   Evaluating a {\bf
defgeneric-options} does not modify any of the methods associated with the
generic function. When a {\bf defgeneric-options} form is evaluated and the
generic function of this name does not exist, it is created with no
methods.

\endsubSection%{Introduction to Generic Functions}

\beginsubSection{Introduction to Methods}

The macro {\bf defmethod} is used to create a method object.  A {\bf
defmethod} form contains the code that is to be run when the
specialized arguments to the generic function cause the method that it
defines to be selected.  If a {\bf defmethod} form is evaluated and a
method object corresponding to the given parameter specializers
already exists, the new definition replaces the old.

Each method has a ``specialized'' lambda list, which indicates which of
its arguments are to be used for method selection.  Only required
parameters can be specialized.   A parameter specializer
 is a list, {\tt ({\it variable-name parameter-specializer\/})},
where {\it parameter-specializer\/} is one of:

\beginlist

\item{\bull} The name of any class.

\item{\bull} ({\bf quote} {\it object\/})

\item{\bull} A symbol naming a standard type class.  These classes are listed
in Figure~1-1.
%corresponding to one of these Common Lisp types:

%\Vskip 1pc!
%\boxfig
%{\bf\tabskip 0pt plus 1fil
%\halign to \hsize{&#\hfil\cr
%array&integer&rational\cr
%bit-vector&list&readtable\cr
%character&long-float&sequence\cr
%compiled-function&null&short-float\cr
%complex&number&single-float\cr
%cons&package&string\cr
%double-float&pathname&symbol\cr
%float&random-state&t\cr
%hashtable&ratio&vector\cr
%}}
%\caption{ \break--use of break gets another line--lgd}
%\endfig

\endlist
 
Note that a parameter specializer cannot be a type specifier list,
such as {\tt ({\bf vector single-float})}.  

Methods can also have arguments not intended to be used for selection;
such parameter specifiers are in {\bf defun} syntax.

A method with no specialized parameters is
a {\bit default method\/}; it is always part of the generic
function, but often shadowed by a more specific method.   A default
method can also have a parameter specializer of {\bf T}; this is the
same as if that parameter had no specializer, since {\bf T} is the 
class of all objects.  An {\bit individual
method\/} is one whose specialized parameter is ({\bf quote} {\it
object\/}); this method is selected if the corresponding argument to the
generic function is {\bf eql} to the {\it object\/}.  
The parameter specializer ({\bf quote} {\it object\/}) is 
more specific than any other specializer.

%Sometimes methods with one specialized parameter are distinguished from
%methods with more than one specialized parameter.  
%Usually, when this is done, a method
%that has only one specialized parameter is called a {\bit classical\/}
%method; a method with more than one specialized parameter is called a
%{\bit multi-method\/}.


Methods can have {\bit qualifiers}, which give the method combination
procedure a way to distinguish between methods.  If a method has one
or more qualifiers it is called a {\bit qualified\/} or {\bit
auxiliary method}.  An unqualified method is called a {\bit primary
method}.  A qualifier is any object other than a list; in other words,
any non-{\bf nil} atom.  By convention, qualifiers are usually keyword
symbols.

\endsubSection%{Introduction to Methods}

\beginsubSection{Congruent Lambda-lists for all Methods of a Generic Function}

The {\it lambda-list\/} argument of {\bf defgeneric-options} specifies
the ``shape'' of lambda lists for the methods of the corresonding
generic function.  All methods for the given generic function must be
congruent with this shape; this implies that the system can determine
whether a call is syntactically correct.  The shape of a lambda list
is defined by the number of required arguments, the number of optional
arguments, whether or not {\bf \&allow-other-keys} appears, the number and
names of keyword arguments, and whether or not {\bf \&rest} is used.

The rules are for congruence are:

[The following is a first approximation of these rules, which need
to be discussed further:]

\numitem{1.}Each method must have the same number of required arguments. 

\numitem{2.}Each method must have the same number of {\bf \&optional}
arguments, but methods can supply different defaults for {\bf
\&optional} arguments.

\numitem{3.}If {\bf \&allow-other-keys} is used by one method, all
methods must use it.

\numitem{4.}If {\bf \&allow-other-keys} is not used, each method must
allow the same number of {\bf \&key} arguments, and these keyword
arguments must have the same keywords across methods.

\numitem{5.}If {\bf \&rest} is used by one method, all methods must use it. 

\numitem{6.}The use of {\bf \&aux} need not be consistent across methods.  

The method receives the same arguments that the generic function 
received. 

\endsubSection%{Congruent Lambda-lists for all Methods of a Generic Function}

\endSection%{Generic Functions and Methods}

\beginSection{Method Selection and Combination}

When a generic function is called with particular arguments, it must decide
what code to execute.  We call this code the {\bit effective method\/} for
those arguments.  The effective method can be one of the methods for the
generic function or a combination of several of them.

Choosing the effective method involves the following decisions: 

\beginlist

\item{\bull} Which method (or methods) to call

\item{\bull} The order in which to call the methods

\item{\bull} Which value (or values) to return 

\item{\bull} Which method to call next when {\bf call-next-method} is used

\endlist

The effective method is determined by the following four-step procedure:

\numitem{1.}Select the set of applicable methods.

Given a generic function and a set of arguments, the applicable methods are
all methods for that generic function whose parameters are satisfied by
their corresponding arguments.  An argument satisfies a parameter if 
one of the following conditions is true:

\beginlist

\item{\bull} The parameter is not specialized.

\item{\bull} The parameter is specialized with a class name {\it C\/} and
{\bf (typep {\it argument\/} '{\it C\/})} is true.  In other words, the
class of the argument is the class named in the specializer or is a
subclass of it.

\item{\bull} The specializer is ({\bf quote} {\it object\/}) and  
the argument is {\bf eql} to the {\it object\/}.

\endlist

\numitem{2.}Sort the applicable methods by precedence order,
putting the most specific method first.

To compare the precedence of two methods, examine their parameters in
order.  The default examination order is from left to right, but an 
alternative order may be specified by the {\bf :argument-precedence-order}
option to {\bf defgeneric-options}.

Compare the specializers of corresponding parameters from each method.  
An unspecialized parameter has a specializer of {\bf t} by default.
The first pair of parameter specializers that are not equal determine the 
precedence.  When a pair of parameter specializers are equal,  
proceed to the next pair and compare them for equality.  

If both parameter specializers are class names, method X is
more specific than method Y if method X's parameter specializer appears
earlier than method Y's parameter specializer in the class precedence list
of the class of the argument.  Due to the way the set of applicable
methods is chosen, the parameter specializers are guaranteed to be present
in the class precedence list of the class of the argument.
{\bf t} is implied at the end of each class precedence list, so it 
is less specific than any other class.

%This seems more confusing than helpful: --Moon
%Note that the ordering is simply alphabetical
%with respect to the argument precedence order and the class precedence list.

If one parameter specializer is ({\bf quote} {\it object\/}), it is more
specific than any class.  If both parameter specializers are quoted
objects, the specializers are equal (otherwise the two methods would
not both have been applicable for this argument).

The resulting list of applicable methods has the most specific
method first and the least specific method at the end.    

\numitem{3.}Apply method combination to the sorted list of applicable methods,
producing the effective method.

Considering the simplest case first, if standard method combination is used
and all applicable methods are primary, the effective method is the 
most specific method.  That method can call the next most specific method
using the macro {\bf call-next-method}.

In general, the effective method is some combination of the applicable
methods.  It is defined by a Lisp form that contains calls to some or all
of the applicable methods, returns the value or values to be returned by
the generic function, and optionally makes some of the methods reachable
via {\bf call-next-method}, rather than calling them directly.  This Lisp
form is the body of the effective method; the object system augments it
with an appropriate lambda-list to make it a function.

Method qualifiers determine the role of each method in the effective
method.  The meaning of the qualifiers of a method is defined entirely by
this step of the procedure.  If an applicable method has an unrecognized
qualifier, this step reports an error and does not include that method in
the effective method.

When standard method combination is used together with qualified methods, 
the effective method is produced as described in the section
``Standard Method Combination''.

The programmer can select another type of method combination by using the
{\bf :method-combination} option of {\bf defgeneric-options}.  This allows
the programmer to customize this step of this procedure without needing to 
consider what happens in the other steps.   (The other steps of this 
procedure can be customized using meta-objects.)

New types of method combination can be defined using the 
{\bf define-method-combination} macro, which is provided in 
the basic Programmer Interface.  The body of the 
{\bf define-method-combination} returns the Lisp form that defines the
effective method.  See the section ``Declarative Method Combination''.

The meta-object level also offers a mechanism for defining new types of
method combination.  The generic function {\bf compute-effective-method}
receives as arguments the generic function, the sorted list of applicable
methods, the name of the method combination type, and the list of options
specified in the {\bf :method-combination} option of
{\bf defgeneric-options}, and returns the Lisp form that defines the
effective method.  The programmer can define a method for
{\bf compute-effective-method} directly, using
{\bf defmacro}, or indirectly, using {\bf define-method-combination}.

\numitem{4.}Apply the effective method to the generic function arguments.

The effective method is called with the same arguments that were passed
to the generic function.  Whatever values it returns are returned as
the values of the generic function.

In the simplest implementation, the generic function would compute the
effective method each time it was called.  In practice, this is too
inefficient for most implementations.  Instead they employ a variety of
optimizations of the four-step procedure, such as precomputation into
tables, compilation, and/or caching to speed things up.  Some illustrative
examples (not exhaustive) are:

\beginlist

\item{\bull} Use a hash table keyed by the class of the arguments to
store the effective method.

\item{\bull} Compile the effective method and save the resulting
compiled-function in a table.

\item{\bull} Recognize the Lisp form as an instance of a pattern of
control structure and substitute a closure of a function that implements
that structure.

\item{\bull} Examine the parameter specializers of all methods for the
generic function and enumerate all possible effective methods.  Combine
these effective methods, together with code to select from among them by
testing the arguments, into a single function and compile it.
Call that function whenever the generic function is called.

\endlist

The Lisp form computed by step~3 as the body of the effective method serves
as a more general interface.  For example, a tool that determines which
methods are called and presents them to the user works by going through the
first three steps of the above procedure and then analyzing the form to
determine which methods it calls, instead of evaluating it.

Separating the procedure of determining the effective method from the
procedure of invoking methods and combining their results, and using a Lisp
form as the interface between these procedures, allows for more optimizations
to the speed of the code and also enables more powerful programming tools
to be written.

\endSection%{Method Selection and Combination}

\beginSection{Standard Method Combination}

Standard method combination is used by default if the programmer does
not specify another type of method combination.   Standard method combination 
recognizes four roles for methods, according to method qualifiers.
Primary methods define the main action of the effective method,
while auxiliary methods modify that action in one of three ways.
The method roles are:

\def\numhangsize{60pt}

\numitem{Primary methods:}These are unqualified methods.  The most specific 
primary method is executed.  Inside the body of a primary method, the macro 
{\bf call-next-method} may be used to pass control to the next most specific 
primary method.  When that method returns, the first primary method can
execute more code, perhaps based on the returned value or values. 
If {\bf call-next-method} is not used, only the most specific 
primary method is executed.   

\numitem{{\bf :before} methods:}These methods have the keyword 
{\bf :before} as their only qualifier.  They specify code that runs before
the primary method.  The most specific {\bf :before} method is executed first.

\numitem{{\bf :after} methods:}These methods have the keyword {\bf :after}
as their only qualifier.  They specify code that runs after the primary
method.  The least specific {\bf :after} method is executed first.

\numitem{{\bf :around} methods:}These methods have the keyword {\bf :around} as
their only qualifier.  The most specific {\bf :around} method is executed. 
Inside the body of an {\bf :around} method, the macro {\bf call-next-method} can be
used to immediately call the ``next method'' (see below).  When the next
method returns, the {\bf :around} method can execute more code, perhaps
based on the returned value or values.  By convention, {\bf :around} methods
almost always use {\bf call-next-method}.

\def\numhangsize{25pt}

The semantics of standard method combination are:

\beginlist

\item{\bull} If there are any {\bf :around} methods, the most specific
{\bf :around} method is executed, and supplies the value or values of the
generic function.

\item{\bull} If an {\bf :around} method uses {\bf call-next-method}, the
next most specific {\bf :around} method is executed, if one is applicable.

\item{\bull} If there are no {\bf :around} methods at all, or if {\bf
call-next-method} is done by the least specific {\bf :around} method, the
other methods are executed in the following way:

\beginlist

\itemitem{--} All the {\bf :before} methods are executed, in
most-specific-first order.

\itemitem{--} The most specific primary method is executed, and supplies
the value or values returned by the generic function (or by {\bf
call-next-method} in the least specific {\bf :around} method).  If it does
{\bf call-next-method}, the second most specific primary method is
executed, and so on until there are no more primary methods.  An error is
signalled if {\bf call-next-method} is used and there is no applicable
primary method to call.

\itemitem{--} All the {\bf :after} methods are executed in
most-specific-last order.

\endlist

\endlist

\beginRemarks

In standard method combination, if there are any applicable methods at all,
then there must be an applicable primary method to produce the value or
values.  In cases where there are applicable methods but no primary method
an error is signalled.

An error is signalled if {\bf call-next-method} is used and there is no
next method remaining.

An error is signalled if {\bf call-next-method} is used in a {\bf :before}
or {\bf :after} method.

Standard method combination allows no more than one qualifier per method.

Running {\bf :before} methods in most-specific-first order while running
{\bf :after} methods in least-specific-first order provides a degree of
transparency.  If class X modifies the behavior of its superclass Y by
adding an auxiliary method, the partitioning of Y's behavior into
primary, {\bf :before}, and {\bf :after} methods is transparent.
Whether class Y defines these methods directly or inherits them from
its superclasses is transparent.
Class X's {\bf :before} method runs before {\it all\/} of class Y's
methods.  Class X's {\bf :after} method runs after {\it all\/} of class Y's
methods.

{\bf :around} methods are an exception to this rule; they do not combine
transparently.  All {\bf :around} methods run before any primary methods
run.  Thus a less specific {\bf :around} method runs before a more specific
primary method.

If only primary methods are used, standard method combination behaves like
CommonLoops.  If {\bf call-next-method} is not used, only the most specific
method is invoked.  That is, more general methods are shadowed by more
specific ones.  If {\bf call-next-method} is used, the effect is the same
as {\bf run-super} in CommonLoops.

If {\bf call-next-method} is not used, standard method combination behaves
like {\bf :daemon} method combination of New Flavors, with {\bf :around}
methods playing the role of whoppers, except that the ability to reverse
the order of the primary methods has been removed.

\endRemarks

\endSection%{Standard Method Combination}


\beginSection{Declarative Method Combination}

The programmer can define new forms of method combination using
the {\bf define-method-combination} macro.  This allows customization
of step~3 of the method combination procedure.  There are two forms
of {\bf define-method-combination}.  The short form is a very
easy to use facility for the cases that have been found to be
most commonly needed.

The long form is more powerful but more verbose.  It resembles
{\bf defmacro} in that the body is an expression that computes
a Lisp form, usually using backquote.  Thus arbitrary control 
structures can be implemented.  The long form also allows arbitrary
processing of method qualifiers.

\beginsubSection{Short Form of Define-method-combination}

% (DEFINE-METHOD-COMBINATION name operator {keyword argument}*)

\Defmac {define-method-combination} {name operator \star{\curly{keyword argument}}}

Defines {\it name\/} as a type of method combination that produces a Lisp form
{\bf ({\it operator method-call method-call...\/})}.   
{\it name\/} is a symbol, usable as a name for this in
the {\bf :method-combination}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}.  
By convention, non-keyword, non-{\bf nil} symbols are usually used.

{\it operator\/} can be the name of a function, the name of a macro, or the
name of a special form.
By convention, {\it name\/} and {\it operator\/} are often the same symbol,
but this is not required.

Keyword options are:

\beginlist

\item{\bull}
{\bf :documentation} {\it string\/} documents the method-combination type.

\item{\bull}
{\bf :identity-with-one-argument} {\it boolean\/} enables an optimization
when {\it boolean\/} is true (the default is false).
If there is exactly one applicable method, and it is a primary method,
it serves as the effective method and {\it operator\/} is not called.
This optimization avoids the need to create a new effective method
and avoids the overhead of a function call.
Use this option with such operators as {\bf progn}, {\bf and}, {\bf $+$},
and {\bf max} that are identity operators when applied to one argument.

\endlist

None of the subforms are evaluated.

A method combination procedure defined this way recognizes two roles for
methods.  An unqualified method is a primary method.  A method with the
keyword symbol with the same name as {\it name\/} as its one qualifier is
also a primary method.  Attaching this qualifier to a primary method
documents that this method is intended for use with an unusual form
of method combination and can make programs easier to understand.

A method with {\bf :around} as its one qualifier is an auxiliary method
that behaves the same as a {\bf :around} method in standard method
combination.

{\bf call-next-method} can only be used in {\bf :around} methods, not in
primary methods.

To specify that a generic function should use this type of method combination, use
the {\bf (:method-combination {\it name\/})}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}.

A method combination procedure defined this way accepts an optional
argument named order, defaulting to {\bf :most-specific-first}.  A value of
{\bf :most-specific-last} reverses the order of the primary methods, without
affecting the order of the auxiliary methods.  Use
the {\bf (:method-combination {\it name\/} :most-specific-last)}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}
to specify this.


This alternate syntax of {\bf define-method-combination} is 
recognized when the second subform is a non-{\bf nil} 
symbol.  A large fraction of the types of method combination needed by 
most programmers can be implemented with this short form, which is 
provided for convenience.   The short form automatically includes 
error-checking and support for {\bf :around} methods, thus saving the
programmer from writing that code, and avoids the need for the programmer to
use the backquote and comma, and learn the more complex syntax of the long form.

%This was a previous wording.   I left it around because I'm
%still thinking about it.   -Sonya 
%This alternate syntax of {\bf define-method-combination} is provided for
%convenience and is recognized when the second subform is a non-{\bf nil}
%symbol.  A large fraction of the types of method combination defined by
%most programmers can be implemented with this short form.  Using the short
%form avoids the ``scariness'' of the long form to new programmers, 
%removes the bother of using backquote and comma correctly, and
%eliminates the temptation to omit error checking and support for
%{\bf :around} methods.

Example:

(define-method-combination and and :identity-with-one-argument t)

(defmethod func :and ((x class1) y) ...)

\endsubSection%{Short Form of Define-method-combination}


\beginsubSection{Long Form of Define-method-combination}

%The following syntax expression needs to be converted to TEX

(DEFINE-METHOD-COMBINATION name lambda-list                     [macro]
      ( {(variable { {qualifier-pattern}+ | predicate}
                   {keyword argument}*)}* )
  {declaration | doc-string}*
  {form}*)

{\it name\/} is a symbol, usable as a name for this in
the {\bf :method-combination}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}.  
By convention, non-keyword, non-{\bf nil} symbols are usually used.

{\it lambda-list\/} is an ordinary lambda-list.  The first argument it
receives is the generic-function.  It also receives any arguments provided
after {\it name\/} in the {\bf :method-combination} option to 
{\bf defgeneric-options} or {\bf defgeneric-options-setf}.

% The generic-function could instead be obtained from a method object, if
% one has a method object in hand and if method objects contain references
% to their generic function (currently under discussion).  Having a method
% object in hand is iffy since a method-group might be empty.
% Hence it seems better to pass the generic function explicitly. --Moon

A list of method-group specifiers follows.  Each specifier selects a subset
of the applicable methods to play a particular role, either by matching
their qualifiers against some patterns or by testing their qualifiers with
a predicate.  These method-group specifiers define all method qualifiers
that can be used with this type of method combination.  If an applicable
method does not fall into any method-group, the system reports the error
that the method is not appropriate for the kind of method-combination being
used.

Each method-group specifier names a variable.  During the execution of the
body forms, the variable is bound to a list of the methods in the
method-group, in most-specific-first order.

A qualifier-pattern is a list or the symbol {\bf *}.  A method matches a
qualifier-pattern if the method's list of qualifiers is {\bf equal} to the
qualifier-pattern, except that the symbol {\bf *} in a qualifier-pattern
matches anything.  Thus a qualifier-pattern can be the empty list {\bf ()}
(which matches primary methods, which are always unqualified), the symbol {\bf *} (which matches all
methods), a true list (which matches methods with the same number of
qualifiers as the length of the list, when each qualifier matches the
corresponding list element), or a dotted list that ends in the symbol
{\bf *} (the {\bf *} matches any number of additional qualifiers).
(True lists are non-dotted lists, as defined in {\it Common Lisp: The
Language\/}.)

Each applicable method is tested against the qualifier-patterns and
predicates in left-to-right order.  As soon as a qualifier-pattern matches
or a predicate returns true, the method becomes a member of the
corresponding method-group and no further tests are made.  Thus if a method
could be a member of more than one method-group, it joins only the first
such group.  If a method-group has more than one qualifier-pattern, a
method need only satisfy one of the qualifier-patterns to be a member of
the group.

The name of a predicate function can appear in place of the
qualifier-patterns in a method-group specifier.  The predicate is called
for each method that has not been assigned to an earlier method-group, with
one argument, the method's qualifier list.  The predicate should return
true if the method should be a member of the method-group.  A predicate is
distinguishable from a qualifier-pattern because it is a symbol other than
{\bf nil} or {\bf *}.

Method-group specifiers can have keyword options after the
qualifier-patterns or predicate.  Keyword options are distinguishable from
additional qualifier patterns because they are not lists nor the symbol
{\bf *}.  The keyword options are:

\def\numhangsize{60pt}

\numitem{{\bf :description} {\it format-string\/}} \break
Programming environment tools use
% TEX won't let me use #' in the next line
{\bf (apply (function format) stream {\it format-string\/}
(method-qualifiers {\it method\/}))}
to print a concise description of a method's role (one or two words).
This keyword option allows the description of a method qualifier to be
defined in the same module that defines the semantic meaning of the
method qualifier.
In most cases {\it format-string\/} will not contain any format directives,
but they are available for generality.
If {\bf :description} is not specified, a default description is generated
based on the variable name, the qualifier patterns, and whether this
method-group includes the primary methods.
The argument {\it format-string\/} is not evaluated.

\numitem{{\bf :order} {\it order\/}} \break
The argument is a form evaluating to {\bf :most-specific-first} or
{\bf :most-specific-last}.  If it evaluates to any other value,
an error is signalled.  This keyword option is a convenience
and does not add any expressive power.  It is provided so that programmers
do not have to write the ugly {\bf case} expression seen in the examples
below, and especially to avoid tempting programmers to omit the error checking.
If {\bf :order} is not specified, it defaults to {\bf :most-specific-first}.

\numitem{{\bf :required} {\it boolean\/}} \break
If the argument is true (not {\bf nil}), and the method-group is empty
(that is, no applicable methods match the qualifier-patterns or satisfy the
predicate), an error is signalled.  This keyword option is a convenience
and does not add any expressive power.  It is provided so that programmers
are not tempted to omit error checking.
If {\bf :required} is not specified, it defaults to {\bf nil}.
The argument {\it boolean\/} is not evaluated.

\def\numhangsize{25pt}

Individual implementations might support other keyword options.
Therefore it is required that all implementations signal an error if
they observe a keyword option that is not implemented locally.

The use of method-group specifiers provides a convenient syntax for the
cliched code that has to be written for every kind of method combination,
to select methods, divide them among the possible roles, and perform the
necessary error checking.  It is possible to perform further filtering of
methods in the body forms, using normal list-processing operations and the
functions {\bf method-qualifiers} and {\bf invalid-method-error}.  It is
permissible to {\bf setq} the variables named in the method-group
specifiers and to bind additional variables.  It is also possible to bypass
the method-group specifier mechanism and do everything in the body forms.
This is accomplished by writing a single method group with {\bf *} as its only
qualifier-pattern; the variable is then bound to a list of all of the
applicable methods, in most-specific-first order.

The body {\it forms\/} compute and return the Lisp form that specifies how
the methods are combined, that is, the effective method.
The body of {\bf define-method-combination} resembles the body of
{\bf defmacro} and uses backquote in a similar way.
The function {\bf make-method-call} is also used in constructing the
Lisp form; it hides the implementation-dependent details of how
methods are called.  Programmers always use {\bf make-method-call} to
translate from the lists of method objects produced by the method-group
specifiers to Lisp forms that invoke those methods.

Erroneous conditions detected by the body should be reported with
{\bf method-combination-error} or {\bf invalid-method-error}; these functions
add any necessary contextual information to the error message and will use
the condition signalling system when and if it is adopted into Common Lisp. 

The body {\it forms\/} are evaluated inside of the bindings created by the
lambda-list and method-group specifiers.  Declarations at the head of
the body are positioned directly inside of bindings created by the
lambda-list, and outside of the bindings of the method-group variables. 
Thus method-group variables cannot be declared.

If a doc-string is present, it documents the method-combination type.  

The functions {\bf make-method-call}, {\bf method-combination-error}, and
{\bf invalid-method-error} can be called from the body {\it forms\/}, or
from functions called by the body {\it forms\/}.  The action of these three
functions can depend on dynamic variables bound by the object system before
calling the method-combination function.  These variables might contain the
parameter list of the effective method or other implementation-dependent
information.

\endsubSection%{Long Form of Define-method-combination}

\beginsubSection{Examples of the Long Form of Define-method-combination}

%These examples could be put in the EXAMPLES field of the DEFINE-METHOD-COMBINATION
%function description.   I think it's better to put them into the Concepts
%chapter and cross-reference them from the function description.

\screen!

;The default method-combination technique
(define-method-combination standard (generic-function)
        ((around (:around))
         (before (:before))
         (primary () :required t)
         (after (:after)))
  (declare (ignore generic-function))
  (make-method-call `(,@around
                      (multiple-value-prog2
                        ,(make-method-call before)
                        ,(make-method-call primary :around t)
                        ,(make-method-call (reverse after))))
                    :around t))

;A simple way to try several methods until one returns non-nil
(define-method-combination and (generic-function)
        ((methods () (:and)))
  (declare (ignore generic-function))
  (make-method-call methods :operator 'and))

;A more complete version of the preceding
(define-method-combination and 
        (generic-function &optional (order ':most-specific-first))
        ((around (:around))
         (primary () (:and)))
  (declare (ignore generic-function))
  ;; Process the order argument
  (case order
    (:most-specific-first)
    (:most-specific-last (setq primary (reverse primary)))
    (otherwise (method-combination-error "~S is an invalid order.~@
    :most-specific-first and :most-specific-last are the possible values."
					 order)))
  ;; Must have a primary method
  (unless primary
    (method-combination-error "A primary method is required."))
  (make-method-call `(,@around
                      ,(make-method-call primary
					 :operator 'and
					 :identity-with-one-argument t))
                    :around t))

;The same thing, using the :order and :required keyword options
(define-method-combination and 
        (generic-function &optional (order ':most-specific-first))
        ((around (:around))
         (primary () (:and) :order order :required t))
  (declare (ignore generic-function))
  (make-method-call `(,@around
                      ,(make-method-call primary
					 :operator 'and
					 :identity-with-one-argument t))
                    :around t))

;This short-form call is behaviorally identical to the preceding
(define-method-combination and and :identity-with-one-argument t)
 
;Order methods by positive integer qualifiers
;:around methods are disallowed to keep the example small
(define-method-combination example-method-combination
        (generic-function)
        ((methods positive-integer-qualifier-p))
  (declare (ignore generic-function))
  (make-method-call (stable-sort methods #'<
                       :key #'(lambda (method)
                                (first (method-qualifiers method))))))

(defun positive-integer-qualifier-p (method-qualifiers)
  (and (= (list-length method-qualifiers) 1)
       (typep (first method-qualifiers) '(integer 0 *))))

% There should also be examples showing how multiple qualifiers
% can be used and showing how the define-method-combination lambda-list
% can be used, but I didn't have time to write good ones and putting in
% bad ones doesn't seem very useful -- Moon

\endscreen!

\endsubSection%{Examples of the Long Form of Define-method-combination}

\endSection%{Declarative Method Combination}


\beginSection{Meta Objects}

\beginsubSection{Metaclasses}

The {\bit metaclass\/} of an object is the class of its class.  The
metaclass determines the form of inheritance used by its classes and the
representation of the instances of its classes.  The metaclass mechanism
can be used to provide particular forms of optimization or to tailor the
\CLOS\ for particular uses (such as the implementation of other object
languages---like Flavors, Smalltalk-80, and Loops).

Any new metaclass must define the structure of its instances, how their
storage is allocated, how their slots are accessed, and how slots and
methods are inherited.  The protocol for defining metaclasses will be
discussed in the chapter ``Meta-Object Protocol.'' 

\endsubSection

\beginsubSection{Standard Metaclasses}

The \CLOS\  defines a number of predefined metaclasses.  These
include the following: 
{\bf standard-type-class}, {\bf structure-class}, and {\bf class}. 

The class {\bf standard-type-class} is a metaclass of all the classes 
that correspond to the standard Common Lisp types specified in
{\it Common Lisp: The Language\/} by Guy L. Steele Jr. 
%except {\bf atom} and {\bf common}.  
These types are listed in Figure~1-1. 
%next sentence removed because it sounds bogus and doesn't add anything. -Sonya
%
%This metaclass allows the special kind of class 
%inheritance rules that are needed to handle the classes that 
%correspond to the standard Common Lisp types.
It is not allowed to make an instance of a standard-type-class using 
{\bf make-instance}, or to use a standard-type-class
as a superclass of a user-defined class. 

The class {\bf structure-class} is a subclass of {\bf standard-type-class}.  
All classes defined by means of {\bf defstruct} are instances of 
{\bf structure-class} or a subclass of {\bf structure-class}.

%The use of {\bf defstruct} implicitly defines a new class which is an
%instance of {\bf structure-class}.

%Instances of {\bf primitive-lisp-type-class} are classes that correspond
%to the basic Common Lisp types.  
%While all classes that correspond to the types
%listed in Figure}1-1 must be instances of either {\bf structure-class}
%or {\bf primitive-lisp-type-class}, no implementation is {\it required\/} to
%have any class that is an instance of {\bf primitive-lisp-type-class}.
%\endsubSection
%
%\endSection

%\beginSection{Meta-Objects}

\CLOS\ provides several predefined meta-objects:  {\bf generic-function} 
(the default class of a generic function), {\bf method} (the default
class of a method), {\bf class} (the default class of a user-defined
class), and the standard method-combination type). 

%Includes objects for classes, objects for methods, objects for generic functions.

%Use: efficiency in implementation; experimentation.

%Allows for variations in the representation of objects, the syntax of
%methods, the combination of methods.

%Can be used to provide tuning and optimization for a particular application.

%\endSection
\endsubSection
\endSection
\endChapter
\bye